1. Field of the Invention
The invention relates in general to signal-processing apparatus and in particular to networks for ordering the values of an input data set and then determining which of the values is the set's Mth-largest. The invention has special relevance in those environments, such as image-..processing, where it is advantageous to perform this ordering and value-determination in real time.
2. Description of the Prior Art
Presented here is the concept of an ordinal-value filter which determines which one of a set of R applied data values is the Mth-largest. When R is odd and M is made equal to ((R+1)/2), the Mth-largest becomes the "middle" value of the data set, having in general an equal number of other data values both larger than and smaller than itself. Such a middle value is designated the median. A median filter is one which determines or selects this median value from an input data set.
Although both the basic concept of the median filter and its use in the field of image processing are well-known, many prior realizations have depended upon time-consuming software routines
Prior-art network concepts capable of being mechanized as hardware-economical, ordinal-value filters which perform the required determinations at the incoming date rate are presented by D. Knuth in Volume 3 of his book, The Art of Computer Programming: Sorting and Searching (1973). See especially the oddeven transposition sorting networks given in Knuth's FIG. 58. on page 241.
The filter mechanization presented in FIG. 1 of this specification can be viewed as a hardware-economical, real-time realization of Knuth's odd-even transposition sorting concepts. It should be noted, however, that the inventions claimed in this specification are considered to be patentably different both from Knuth's concepts and from the mechanization of FIG. 1, as well as from the network concepts and mechanizations presented in the incorporated applications.
A real-time ordinal-value-filtering capability is extremely useful, especially, for example, in those situations where the ordinal-value processing of dynamic images is of greatest value when it can be performed as the images are occurring.